package leetcode.top100;


import utils.TreeNode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * @date 2019/11/8 0008 下午 3:09
 * 寻找两个节点的最低公共祖先
 * <p>
 * 出现特殊情况：一个节点是另一个节点的祖先，就返回离根节点最近的那个节点
 */
public class Code236_FindCommonParent_寻找公共祖先 {

    /**
     * case1:
     * 若是BST：
     * 公共祖先的左孩子肯定小于右孩子.
     */
    public static TreeNode getLastCommonNodeBST(TreeNode root, TreeNode left, TreeNode right) {
        TreeNode treeNode = null;
        if (root == null || left == null || right == null || left.val > right.val) {
            return null;
        }
        //当前节点比右孩子都大，那么说明左右孩子都在左子树
        if (root.val >= right.val) {
            treeNode = getLastCommonNodeBST(root.left, left, right);
        }
        //当前节点比左孩子都小，那么说明左右孩子都在右子树
        if (root.val <= left.val) {
            treeNode = getLastCommonNodeBST(root.right, left, right);
        }
        //当前节点比左小，比右大，说明是最低公共祖先
        if (root.val >= left.val && root.val <= right.val) {
            return root;
        }
        return treeNode;
    }

    /**
     * case3:
     * 若是二叉树，并且有父节点，则转为把这两个节点分别到根节点形成两个链表，
     * 找这两个链表的第一个公共节点。
     */
    private static class Tree {
        int val;
        Tree left;
        Tree right;
        Tree parent;
    }

    public static Tree getLastCommonNodeWithParent(Tree root, Tree left, Tree right) {
        if (root == null || left == null || right == null) {
            return null;
        }
        /**
         * 注意：下面也可以直接用set存left直到root，不用真正给两个链表，想象出两个链表即可。
         */
        //转成两个链表
        List<Tree> list1 = new LinkedList<>();
        List<Tree> list2 = new LinkedList<>();
        while (left.parent != null) {
            list1.add(left);
            left = left.parent;
        }
        while (right.parent != null) {
            list2.add(right);
            right = right.parent;
        }
        //找两个链表的第一个公共节点
        Set<Tree> set = new HashSet<>();
        for (int i = 0; i < list1.size(); i++) {
            set.add(list1.get(i));
        }
        for (int i = 0; i < list2.size(); i++) {
            if (set.contains(list2.get(i))) {
                return list2.get(i);
            }
        }
        return null;
    }


    /**
     * case3:是普通的树，并且没有父指针
     * 方法2：
     * 需要额外空间O(nlogn)，
     * 1、拿到根节点到left和根节点到right的路径，放入数组或链表.做两次先序遍历，O(n)
     * 2、求数组或链表的最后一个不同元素
     * 这里有两种方法，第一种是从当前节点形成链表到root，第二种是从root形成链表到当前节点
     */
    public static TreeNode getLastCommonNodeWithOutParent2(TreeNode root, TreeNode left, TreeNode
            right) {
        if (root == null || left == null || right == null) {
            return null;
        }

        List<TreeNode> path1 = new LinkedList<>();
        List<TreeNode> path2 = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        //1 分别找到根节点到两个节点的路径
        //这里有两种方法，第一种是从当前节点形成链表到root，第二种是从root形成链表到当前节点
        getPath(root, left, path1, stack);
        System.out.println("path1:");
        path1.forEach(p -> System.out.print(p.val + " ->"));
        System.out.println();
        stack.clear();
        getPath(root, right, path2, stack);
        System.out.println("path2:");
        path2.forEach(p -> System.out.print(p.val + " ->"));
        System.out.println();
        //2 找到这两个链表的最后一个公共节点，就是两个节点的最低公共节点
//        return getLastCommonNode(path1,path2);
        return getFirstCommonNode(path1, path2);
    }

    private static TreeNode getFirstCommonNode(List<TreeNode> path1, List<TreeNode> path2) {
        Set<TreeNode> set = new HashSet<>();
        for (int i = 0; i < path1.size(); i++) {
            set.add(path1.get(i));
        }
        for (int i = 0; i < path2.size(); i++) {
            if (set.contains(path2.get(i))) {
                return path2.get(i);
            }
        }
        return null;
    }

    //找两个链表的最后一个公共节点
    private static TreeNode getLastCommonNode(List<TreeNode> path1, List<TreeNode> path2) {
        int index = 0;
        while (index < path1.size() && index < path2.size()) {
            if (path1.get(index) != path2.get(index)) {
                break;
            }
            index++;
        }
        //已经找到最后一个公共节点
        return path1.get(index - 1);

    }

    /**
     * 先序遍历
     */
    private static void getPath(TreeNode root, TreeNode destination, List<TreeNode> path,
                                LinkedList<TreeNode> stack) {
        if (root == null) {
            return;
        }
        //
        stack.push(root);
        //到达目标节点
        if (root == destination) {
            //从当前节点到根节点建立链表，对应方法是寻找第一个公共节点
            // for (int i = 0; i <= stack.size() - 1; i++) {
            //从跟节点到当前节点建立链表，对应方法是寻找最后一个公共节点
            for (int i = stack.size() - 1; i >= 0; i--) {
                path.add(stack.get(i));
            }
            return;
        }
        getPath(root.left, destination, path, stack);
        getPath(root.right, destination, path, stack);
        //弹出节点
        stack.pop();
    }

    public static void main(String[] args) {
        /**********BST ***************/
        /*TreeNode head = new TreeNode(5);
        head.left = new TreeNode(4);
        head.right = new TreeNode(6);
        head.left.left = new TreeNode(3);
        head.right.right = new TreeNode(7);
        TreeNode treeNode = getLastCommonNodeBST(head, head.left.left, head.left);
        System.out.println("BST： = " + treeNode.val);*/
        TreeNode head = new TreeNode(3);
        head.left = new TreeNode(5);
        head.left.left = new TreeNode(6);
        head.left.right = new TreeNode(2);
        head.left.right.left = new TreeNode(7);
        head.left.right.right = new TreeNode(4);
        head.right = new TreeNode(1);
        head.right.left = new TreeNode(0);
        head.right.right = new TreeNode(8);
        /**********test getPath **********/

        System.out.println("common:" +
                getLastCommonNodeWithOutParent2(head, head.left, head.right).val);
    }

   /* TreeNode head = new TreeNode(3);
    @Before
    public void init(){
        head.left = new TreeNode(5);
        head.left.left = new TreeNode(6);
        head.left.right = new TreeNode(2);
        head.left.right.left = new TreeNode(7);
        head.left.right.right = new TreeNode(4);
        head.right = new TreeNode(1);
        head.right.left = new TreeNode(0);
        head.right.right = new TreeNode(8);
    }


    //pass
    @Test
    public void testGetPath_testGestLastCommonNode(){
        List<TreeNode> path1 = new LinkedList<>();
        List<TreeNode> path2 = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        getPath(head,head.left.left,path1,stack);
        for (TreeNode treeNode : path1) {
            System.out.print(treeNode.val+" -> ");
        }
        System.out.println();

        stack.clear();

        getPath(head,head.left.right,path2,stack);
        for (TreeNode treeNode : path2) {
            System.out.print(treeNode.val+" -> ");
        }
        System.out.println();
        //test getlastCommonNode
        System.out.println("last commonNode :"+getLastCommonNode(path1, path2).val);
    }*/
}
